/**
 *给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 *
 *
 *
 * 注意：
 *
 * 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
 * 如果 s 中存在这样的子串，我们保证它是唯一的答案。
 *思路：滑动窗口
 * 思路和算法
 *
 * 本问题要求我们返回字符串 s中包含字符串 t 的全部字符的最小窗口。我们称包含 t 的全部字母的窗口为「可行」窗口。
 *
 * 我们可以用滑动窗口的思想解决这个问题。在滑动窗口类型的问题中都会有两个指针，一个用于「延伸」现有窗口的 r 指针，和一个用于「收缩」窗口的 l 指针。在任意时刻，只有一个指针运动，而另一个保持静止。我们在 ss 上滑动窗口，通过移动 rr 指针不断扩张窗口。当窗口包含 tt 全部所需的字符后，如果能收缩，我们就收缩窗口直到得到最小窗口。
 *
 *如何判断当前的窗口包含所有 t 所需的字符呢？我们可以用一个哈希表表示 t 中所有的字符以及它们的个数，用一个哈希表动态维护窗口中所有的字符以及它们的个数，如果这个动态表中包含 t 的哈希表中的所有字符，并且对应的个数都不小于 t 的哈希表中各个字符的个数，那么当前的窗口是「可行」的。
 *
 * 注意：这里 t 中可能出现重复的字符，所以我们要记录字符的个数。
 *
 * 作者：LeetCode-Solution
 * 链接：https://leetcode.cn/problems/minimum-window-substring/solution/zui-xiao-fu-gai-zi-chuan-by-leetcode-solution/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 */
class MinWindow {
   
    public String minWindow(String s, String t) {
     Map<Character,Integer> str=new HashMap<>();//主串
    Map<Character,Integer> child=new HashMap<>();//子串
    int tLen=t.length();
    for(int i=0;i<tLen;i++){
        char ch=t.charAt(i);
        child.put(ch,child.getOrDefault(ch,0)+1);
    }
    int len=Integer.MAX_VALUE;
    int ansLeft=-1;
    int ansLight=-1;
    int l=0;
    int r=-1;
    int sLen=s.length();
    while(r<sLen){
        r++;
        if(r<sLen&&child.containsKey(s.charAt(r))){
            str.put(s.charAt(r),str.getOrDefault(s.charAt(r),0)+1);
        }
        while(check(str,child)&&l<=r){
            if(r-l+1<len){
                len=r-l+1;
                ansLeft=l;
                ansLight=l+len;
            }
            if(str.containsKey(s.charAt(l))){
                str.put(s.charAt(l),str.getOrDefault(s.charAt(l),0)-1);
            }
            l++;
        }
        
    }
    return ansLeft==-1?"":s.substring(ansLeft,ansLight);
}
    public boolean check(Map<Character,Integer> str,Map<Character,Integer> s){
        for(Map.Entry<Character,Integer> entry:s.entrySet()){
            Character key=entry.getKey();
            Integer val=entry.getValue();
            if(str.getOrDefault(key,0)<val){
                return false;
            }
        }
        return true;
    }
}